package chapter03_binaryTree.lowestAncestor;

import chapter03_binaryTree.Node;
import sun.awt.image.ImageWatched;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 描述：
 *      找到两个结点最近的公共祖先
 *      再进阶：给定二叉树的头结点head，同时给定所有想要进行的查询，
 *                二叉树的结点个数为N，查询的条数为M，时间复杂度请达到O(N+M)
 *      tarjin算法求解，流程：
 *      1、初始化：
 *          1）遍历二叉树，创建以每个结点自身为集合的集合组
 *          2）创建queryMap和indexMap，两者的结果使用邻接表，相当于一个key对应一个链表，一对多的关系
 *              queryMap记录与key相关的查询任务，indexMap与queryMap联合使用记录key相关的查询任务结果应该存放在哪个下标
 *      2、中序遍历的过程中求解：（遍历每个结点会来到三次）
 *          1）第二次来到node，设置node所属集合的祖先结点为node，如果左孩子不为空，则合并node当前集合和node的左孩子所属的集合，设置合并后集合的祖先结点为当前node。
 *                  如果在queryMap中看是否有与node相关的查询任务，比如有node与node2的任务，
 *                      如果node2已经设置过祖先结点，那么说明这个任务可以处理，则node和node2的最近的祖先结点为node当前的祖先结点，删除node2这个任务
 *                      如果node2没有设置过祖先结点，那么说明这个任务还不能处理，但是也可以删除node2这个任务，因为这个任务会在遍历到node2的时候被处理
 *                  与然后向有孩子遍历
 *          2）第三次来到node，如果右孩子的集合不为空合并node当前所属的集合和node右孩子所属的集合，设置合并后集合的祖先结点为node
 *
 *      细节：
 *      1）查询某个结点所属的集合和合并集合的操作为了提高效率，可以使用并查集数据结构
 *      2）设置结点的祖先结点可以使用哈希表ancestorMap来操作，key表示当前结点，value表示祖先结点
 * @author hl
 * @date 2021/5/31 16:03
 */
public class TarjanQuery {

    //入口
    public Node[] tarjinQuery(Node head, Query[] queries){
        return new Tarjan().query(head, queries);
    }
    static class Tarjan{
        HashMap<Node, LinkedList<Node>> queryMap;
        HashMap<Node, LinkedList<Integer>> indexMap;
        //存储当前结点祖先结点
        HashMap<Node, Node> ancestorMap;
        DisjiontSets disjiontSets;

        public Tarjan() {
            queryMap = new HashMap<>();
            indexMap = new HashMap<>();
            ancestorMap = new HashMap<>();
            disjiontSets = new DisjiontSets();
        }
        public Node[] query(Node head, Query[] queries){
            if(head == null || queries == null || queries.length == 0){
                return null;
            }
            Node[] ans = new Node[queries.length];
            setQueris(queries, ans);
            disjiontSets.makeSets(head);
            setAnswers(head, ans);
            return ans;
        }

        private void setQueris(Query[] queries, Node[] ans) {
            Node o1 = null;
            Node o2 = null;
            for (int i = 0; i < queries.length; i++) {
                o1 = queries[i].o1;
                o2 = queries[i].o2;
                if (o1 == o2 || o1 == null || o2 == null) {
                    //此情况下可以直接设置答案
                    ans[i] = o1 != null ? o1 : o2;
                }else{
                    if (!queryMap.containsKey(o1)) {
                        queryMap.put(o1, new LinkedList());
                        indexMap.put(o1, new LinkedList());
                    }
                    if (!queryMap.containsKey(o2)) {
                        queryMap.put(o2, new LinkedList());
                        indexMap.put(o2, new LinkedList());
                    }
                    queryMap.get(o1).offer(o2);
                    indexMap.get(o1).offer(i);
                    queryMap.get(o2).offer(o1);
                    indexMap.get(o2).offer(i);
                }
            }
        }
        private void setAnswers(Node head, Node[] ans) {
            if(head == null){
                return ;
            }
            setAnswers(head.left, ans);
            //合并左孩子所在的集合
            disjiontSets.union(head, head.left);
            //设置合并后的集合的祖先结点为当前结点
            ancestorMap.put(disjiontSets.findFather(head), head);
            setAnswers(head.right, ans);
            disjiontSets.union(head, head.right);
            ancestorMap.put(disjiontSets.findFather(head), head);
            //开始处理head相关的任务
            LinkedList<Node> nlist = queryMap.get(head);
            LinkedList<Integer> ilist = indexMap.get(head);
            Node node = null;
            Node nFather = null;
            int index = 0;
            while(!nlist.isEmpty() && !ilist.isEmpty()){
                node = nlist.poll();
                index = ilist.poll();
                nFather = disjiontSets.findFather(node);
                if (ancestorMap.containsKey(nFather)) {
                    ans[index] = ancestorMap.get(nFather);
                }
            }
        }
    }

    static class Query{
        public Node o1;
        public Node o2;

        public Query(Node o1, Node o2) {
            this.o1 = o1;
            this.o2 = o2;
        }
    }
}
